package com.briup.corejava.day06;

import java.util.Arrays;

/**
 * 排序算法：
 * 1、冒泡排序
 * 2、选择排序
 * 3、插入排序
 * 4、希尔排序
 */
public class Test3 {
    // 冒泡排序
    public static int[] bubbleSort(int[] arr){
        // 核心点：理解两层循环的含义和次数的选择
        //1、选数排序
        for(int i=0;i<arr.length-1;i++){
            // 2、选数进行比较
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j] > arr[j+1]){
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
        return arr;
    }
    // 插入排序
    public static int[] insertion(int[] arr){
        // 1、选数
        for(int i=1;i<arr.length;i++){
            // 2、选数比较
            // 用变量将要排序的当前数保存
            int value = arr[i];
            // int j = i-1; 书上
            // index 代表 将要插入的位置
            int index = 0;
            for(int j = i;j>=1;j--){
                if(value < arr[j-1]) {
                    arr[j] = arr[j - 1];
                }
                else {
                    index = j;
                    break;
                }
            }
            // 3、将当前数插入到指定位置
            arr[index] = value;
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {3,4,6,5,7,1,9};
        // System.out.println(Arrays.toString(bubbleSort(arr)));
        System.out.println(Arrays.toString(insertion(arr)));
    }
}
